package sort;

import java.util.Arrays;

public class CountSort {  // 计数排序 鸽巢原理   O(N + len)
    //  使用场景：给出指定范围内数据的排序
    public static void main(String[] args) {
        int[] array = {27,15,19,28,18,6};
        countSort(array);
    }
    public static void countSort(int[] array){
        int max = array[0];
        int min = array[0];
        // 求出最大和最小元素值
        for (int i = 1; i < array.length; i++) {  // O(n)
            if(array[i] < min){
                min = array[i];
            }
            if(array[i] > max){
                max = array[i];
            }
        }
        // 根据最大最小的差值确定数组长度
        int len = max - min + 1;
        int[] nums = new int[len];
        // 遍历原始数组，统计计数数组中每个值出现的次数
        for (int i = 0; i < array.length; i++) {  // O(N)
            nums[array[i] - min]++;
        }
        // 遍历计数数组 进行打印
        for (int i = 0; i < nums.length; i++) {  // O(max-min)
            while (nums[i] != 0){
                System.out.print(i + min + " ");
                nums[i]--;
            }
        }
    }
}
